Black Crawling Systems Archive Release 1.0/Black Crawling Systems Archive Release 1.0 (L0pht Heavy Industries, Inc.)(1997).ISO/blackcrwl/encrypt/RITTER-C.TXT

Internet Message Format | 1996-06-08 | 14KB

Path: msuinfo!midway!ncar!elroy.jpl.nasa.gov!usc!cs.utexas.edu!peyote!ritter
From: [e-mail] (Terry Ritter)
Newsgroups: sci.crypt
Subject: Design of Cryptosystem CLOAK
Keywords: cipher dynamic substitution additive RNG cloak
Message-ID: <[e-mail]>
Date: 16 Nov 90 21:32:32 GMT
Distribution: usa
Organization: Capital Area Central Texas Unix Society, Austin, TX
Lines: 294


     Apparently something went wrong with the first post -- if this
is a duplicate, sorry!


      If you found the source for the CLOAK cipher a bit much, or
even irritating, you are not alone.  Gee, folks, I just don't use
C much; I prefer Turbo Pascal.  A short "theory" document was
included in the distribution file CLOAK.ZIP which is on many
bulletin boards.  But I was worried about message length, and did
not include it in the CLOAK posting here.

      Basically, CLOAK is a stream cipher, with an improved and non-
linear combiner design (instead of the usual linear exclusive-OR),
and an improved Random Number Generator (with up to 44K of internal
state).  The sequence of operations is approximately as follows:

      * A textual User Key is processed into 992 bits
      * The User Key bits initialize a large RNG
      * The RNG is extended
      * A 992-bit "really random" Message Key is created
      * The RNG is used to XOR-cipher the Message Key
      * The plaintext Message Key re-inits the RNG
      * The RNG is extended to operational length
      * The RNG is used to init the Dynamic Substitution tables
      * The RNG and Dynamic Substitution encipher plaintext data

      Since an enciphered Message Key is added to every enciphered
file anyway, additional header information is also added.  This
includes a flag to indicate "enciphered," and values which indicate
the cipher technique being used.  In this way, the design can be
extended in the future, and yet still remain compatible with
existing enciphered files.

      The cryptographic RNG is an Additive design, which is based on
some arbitrary primitive mod 2 polynomial; GFSR designs using
trinomials of degree 521 have been reported.  The CLOAK RNG uses
particular primitive 9-nomials found by the author, and includes a
selection between degrees 1279, 4253, and 11213 when enciphering.
This is a very big RNG.

      Should you wish to work on breaking CLOAK, please first work
on breaking the Dynamic Substitution demo DYNSUB.PAS posted here
last year.  Using the Turbo internal LCG RNG, without a message
key, and just a single level of Dynamic Substitution, an attack
should be far easier, and may demonstrate methods which could be
used on the larger system.




                          CLOAK DESIGN THEORY

                             Terry Ritter
                              26 Oct 1990


CLOAK was designed to be a strong cipher.  Of course, most cipher
programs produce ciphertext which seems to be complex, but very few
available ciphers could be expected to win a confrontation with
professional cryptanalysts and their fast computers.

CLOAK was designed to be as simple as possible, so that the design
could be fully revealed.  The usual practice is to invent a
"proprietary" cipher, and keep the design secret.  What this really
means is that serious cryptanalysts will know the design, while
buyers and users will not; a strange situation indeed.

At this point in the public development of cryptography, there is
still no practical cipher which is provably secret.  Since the
design of CLOAK is open to examination, each expert may come to
their own conclusion as to its strength.


STREAM CIPHERS
      CLOAK is an example of a stream cipher.  The classical Vernam
stream cipher simply combines plaintext data with the output from
a random number generator in an additive combiner, which is often
a single exclusive-OR gate or XOR operation.

Unfortunately, additive combiners are inherently susceptible to
"known plaintext" attacks.  Moreover, most random number generators
have only a tiny amount of internal state, and are easy to break.
Such a system is really a "toy" cipher.

CLOAK improves upon the classical stream cipher design with a
completely new class of cryptographic combiner (patent pending), a
very large cryptographic random number generator, and "really
random" message keys.

Alternative design approaches include DES, which is now rather
small, and RSA, which is slow and complex.  Public-key systems may
seem to improve the key-distribution situation, but they also
forego the inherent source verification of a secret-key system.
This can be overcome only with complex and precise protocols, thus
adding even more complexity to the system.

CLOAK is a secret-key system, which means that it is necessary to
somehow get the secret key to the far end, so that enciphered
messages may be deciphered.  However, once this is done, only those
possessing the secret key may cipher messages in that key.  A
secret-key system thus mimics the use of a house key, and has
similar problems and risks.


DYNAMIC SUBSTITUTION COMBINER
      The new cryptographic combiner can be described as an
extension of classical Simple Substitution.  In simple
substitution, each plaintext data value is translated into a
ciphertext value using a substitution table.  The innovation of
Dynamic Substitution is to re-arrange the content of the
substitution table after every substitution operation.  In this
case, the just-used substitution is exchanged with some
substitution selected at random.

The result is a non-linear combiner with a substantial amount of
internal state.  Only non-linear combiners make sense when several
are used in sequence; linear additive combiners do not.

In CLOAK, I have used a two-level Dynamic Substitution design.  The
first level randomizes the incoming data, and the second level has
16 separate combiners selected for use at random.  Because the
second-level combiners are used at random, it should be difficult
for a cryptanalyst to work on the content of any particular
substitution table.

Dynamic Substitution technology is patent-pending.


CRYPTOGRAPHIC RANDOM NUMBER GENERATOR
      The usual computer-language random number generator (RNG) is
a 32-bit linear congruential generator (LCG), and can be solved
very easily given one, or perhaps a few of the random values.  This
is a very weak cryptographic design.

The generator I selected for use in CLOAK is the Additive RNG, as
discussed in Knuth II.

The strength of an RNG is at least partially related to the amount
of its internal state, and the ones designed for statistical
service are rather small.  But the Additive generator is easily
customized, and can be made one or more bytes wide.  For CLOAK, the
width has been set at 32 bits.

The Additive generator can also be made as long as desired,
provided that one can find primitive mod 2 polynomials of large
degree.  For CLOAK primitives have been found at degrees 1279, 4253
and 11213.  Thus, the amount internal state can be 11213 times as
large as the usual computer language LCG RNG.

There are billions of acceptable polynomials; the particular ones
selected for use in CLOAK are protected by copyright.


JITTERIZER
      Despite its size, the Additive generator is nonetheless a
linear system, and thus "easily" solved (assuming a cyptanalyst
gets past the combiners).  Naturally, the manipulation of 11,000
equations in 11,000 unknowns of 32-bits each might be expected to
slow cryptanalysis somewhat.  Nevertheless, it is still necessary
to add some sort of isolation mechanism to hide the true sequence
from analysis.

For CLOAK, I have devised a mechanism which periodically deletes
some of the Additive RNG result values from the output stream.  A
random number of values are deleted after a random number of steps.
In addition, each group of values is given a separate value offset.
This should make cryptanalysis a real exercise; certainly the
jitterizer cannot be expected to make cryptanalysis any easier.


THE MESSAGE KEY
      An RNG will produce a particular sequence of random numbers
after being initialized from a particular key.  Thus, when the
usual stream cipher is used twice with the same key, the messages
will be combined with the same sequence.  But one of the properties
of additive combiners is that repeated sequences can "canceled
out," thus leaving a combination of two plaintext messages.  Such
a combination is likely to be broken easily.

Consequently, it is important that the same sequence not be used
for each message.  This could be done, for example, by having a
different User Key for each message.  But this is surely
unacceptable, for who could remember that many keys?  Who could
transfer that many keys to the far end with any degree of secrecy?

An alternative is to use a different key for each message, but do
so only internally.  Each Message Key is enciphered and included in
the message header; the User Key is used to encipher and thus
protect the message key.

Each message key is a "really random" value which is created
dynamically for each message.  Because the message key is a truly
arbitrary value, and since most cryptanalysis methods require that
a message "make sense," an enciphered message key will be very
difficult to crack.

Another advantage of the message key is that it can be made quite
large, as well as random.  CLOAK uses a message key consisting of
31 values of 32 bits each; a 124-byte message key (992 bits).  This
is enough to directly initialize a degree-31 Additive RNG, which is
then stepped until enough data are produced for a degree-127 RNG,
etc.  Thus, the "really random" message key automatically satisfies
many of the questions about a statistically correct initialization
of the RNG.  It also reduces the need for extreme length in the
user key.


THE USER KEY
      Although the User Key is used only to protect the message key,
it must initialize an RNG in order to do so.  This initialization
should be as arbitrary as possible.  I decided to use LFSR or CRC
technology to perform a polynomial division of the textual key, and
use remainders as the initialization value.

The user key is processed by 32 degree-31 polynomials, thus
producing 32 different results of 31 bits each.  By eliminating the
unused bits, 31 values of 32 bits each are produced; this is
exactly the right amount of data to initialize a degree-31 Additive
RNG.  By stepping the Additive RNG, it will eventually fill enough
to initialize a degree-127 RNG, and so on.

CLOAK collects the user key from the keyboard into a string with a
maximum length of 255 bytes; thus, up to 2040 bits of randomness
are collected.  This is then reduced (or expanded) to the 992 bits
needed for degree-31 Additive RNG initialization.  CLOAK does not
insist on a long user key, but the serious user will create very
unique keys of 30 characters or longer.

There are millions of acceptable degree-31 primitive mod 2
polynomials; the particular ones selected for CLOAK are protected
by copyright.



SELECTED BIBLIOGRAPHY
      .  Beker, H. and F. Piper.  1982.  Cipher Systems.  John
Wiley: New York.
      .  Blum, L., M. Blum and M. Shub.  1986.  A Simple
Unpredictable Pseudo-Random Number Generator.  SIAM Journal of
Computing.  15: 364-383.
      .  Chaitin, G.  1975.  Randomness and mathematical proof.
Scientific American.  232(5): 47-52.
      .  Ciarcia, S.  1986.  Build a Hardware Data Encryptor.
Byte.  Sept: 97-111.
      .  Devours, C., D. Kahn, L. Kruh, G. Mellen, B. Winkel.
1987.   Cryptology Yesterday, Today, and Tomorrow.  Artech House:
Norwood, MA.
      .  Geffe, P.  1973.  How to protect data with ciphers that
are really hard to break.  Electronics.  46(1): 99-101.
      .  Golomb, S.  1982 (original 1967).  Shift Register
Sequences.  Aegean Park Press:  POB 2837, Laguna Hills, CA 92653.
      .  Kahn, D.  1967.  The Codebreakers.  Macmillan: New York.
      .  Knuth, D.  The Art of Computer Programming, Vol. 2,
Seminumerical Algorithms.  2nd ed.  Addison-Wesley: Reading,
Massachusetts.
      .  Kochanski, M.  1987.  A Survey of Data Insecurity
Packages.  Cryptologia.  XI(1): 1-15.
      .  Kochanski, M.  1988.  Another Data Insecurity Package.
Cryptologia.  XII(3): 165-173.
      .  L'Ecuyer, P. and R. Proulx.  1989.  About Polynomial-
Time "Unpredictable" Generators.  Proceedings of the 1989 Winter
Simulation Conference.  467-476.
      .  Lu, S.  1979.  The Existence of Good Cryptosystems for
Key Rates Greater than Message Redundancy.  IEEE Transactions on
Information Theory.  IT-25(4): 475-477.
      .  MacWilliams, F. and N. Sloane.  1977.  The Theory of
Error-Correcting Codes.  North Holland:  Amsterdam / New York.
      .  Marsaglia, G.  1984.  A current view of random number
generators.  Proceedings of the Sixteenth Symposium on the
Interface Between Computer Science and Statistics.  3-10.
      .  Marsaglia, G. and L. Tsay.  1985.  Matrices and the
Structure of Random Number Sequences.  Linear Algebra and its
Applications.  67: 147-156.
      .  Pearson, P.  1988.  Cryptanalysis of the Ciarcia
Circuit Cellar Data Encryptor.  Cryptologia.  12: 1-10.
      .  Plauger, P.  1988.  Locking the Barn Door.  Computer
Language.  October, 17-22.
      .  Retter, C.  1984.  Cryptanalysis of a Maclaren-
Marsaglia System.  Cryptologia.  8(2): 97-108.  (Also see 8(4):
374-378.)
      .  Retter, C.  1985.  A Key-Search Attack on Maclaren-
Marsaglia Systems.  Cryptologia.  9(2): 114-130.
      .  Ritter, T.  1990.  Substitution Cipher with Pseudo-
Random Shuffling:  The Dynamic Substitution Combiner.  Cryptologia.
XIV(4): 289-303.
      .  Siegenthaler, T.  1985.  Decrypting a Class of Stream
Ciphers Using Ciphertext Only.  IEEE Transactions on Computers.
C-34(1): 81-85.
      .  Vahle, M. and L. Tolendino.  1982.  Breaking a Pseudo
Random Number Based Cryptographic Algorithm.  Cryptologia.  6(4):
319-328.
      .  Wolfram, S.  1986.  Random Sequence Generation by
Cellular Automata.  Advances in Applied Mathematics.  7: 123-169.